package alog;

import java.util.*;

/**
 * 排序算法手撕
 */
public class Sort {
    public static void main(String[] args) {
        int[] nums = {4,2,8,3,7,0,-1,41,4,2};
//        quickSort(0,nums.length - 1, nums);
//        bubbleSort(nums);
//        SelectSort(nums);
//        insertionSort(nums);
//        heapSort(nums);
        merger_sort(nums, 0, nums.length - 1, new int[nums.length]);
        for(int i : nums)
            System.out.print(i + " ");
    }


    //快速排序-不稳定
    public static void quickSort(int left, int right, int[] nums){
        if(left >= right)
            return;
        int i = left, j = right;
        while (i < j)
        {
            while (i < j && nums[j] >= nums[left])
                j--;
            while (i < j && nums[i] <= nums[left])
                i++;
            if(i < j)
            {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }

        }
        int tmp2 = nums[left]; //基准数据
        nums[left] = nums[i];
        nums[i] = tmp2;
        quickSort(left, i - 1, nums);
        quickSort(i + 1, right, nums);
    }



    //冒泡-稳定
    public static void bubbleSort(int[] nums){
        for(int i = 0; i < nums.length - 1; i++){
            boolean flag = true;
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if(nums[j] > nums[j + 1])
                {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    flag = false;
                }
            }
            if(flag)
                break;
        }
    }



    //简单选择排序-不稳定
    public static void SelectSort(int[] nums){
        for (int i = 0; i < nums.length - 1; i++) {
            int min = nums[i];
            int t = i;
            for (int j = i + 1; j < nums.length; j++) {
                if(min > nums[j])
                {
                    min = nums[j];
                    t = j;
                }
            }
            nums[t] = nums[i];
            nums[i] = min;
        }
    }

    /**
     * 直接插入排序，前面是有序的，稳定
     */

    public static void insertionSort(int[] nums){
        for (int i = 1; i < nums.length; i++) {
            int j = i - 1;
            int temp = nums[i];
            while(j >= 0 && nums[j] > temp){
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = temp;
        }
    }

    // 堆排序，不稳定
    //堆排序是选择排序中利用堆进行排序的不稳定的一种排序算法。若在输出堆顶的最小值（最大值）后，
    // 使得剩余 n-1 个元素的序列又建成一个堆，则得到 n 个元素的次小值（次大值）。
    // 通过反复进行上述操作，便能得到一个有序序列，这个过程称之为堆排序,其存储结构是顺序存储，逻辑结构是二叉树

    public static void heapSort(int[] nums){
        int n = nums.length;
        //从第一个不是叶子节点的节点开始初始化大根堆
        for (int i = n / 2 - 1; i >= 0 ; i--) {
            adjust_heap(nums, n, i);
        }

        //每次选取堆顶（最大）与最后一个交换，并调整堆，堆顶开始调整
        for (int j = n - 1; j >= 0; j--)
        {
            int temp = nums[0];
            nums[0] = nums[j];
            nums[j] = temp;
            adjust_heap(nums, j, 0);
        }
    }
    //调整堆
    public static void adjust_heap(int[] nums, int len, int parent){
        int leftChild = parent * 2 + 1;
        int rightChild = leftChild + 1;
        //左右孩子里面选最大的
        if(leftChild < len){
            int max_value = leftChild;
            if(rightChild < len){
                if(nums[rightChild] > nums[max_value])
                    max_value = rightChild;
            }
            //如果左右孩子大于parent，则需要交换，并且调整左堆或者右堆
            if(nums[parent] < nums[max_value]){
                int temp = nums[parent];
                nums[parent] = nums[max_value];
                nums[max_value] = temp;
                adjust_heap(nums, len, max_value);
            }
        }
    }

    /**
     * 归并排序
     */
    public static void merger_sort(int[] nums, int left, int right, int[] temp){
        if(left >= right)
            return;
        //寻找中间节点
        int mid = left + (right - left) / 2;
        //左右递归
        merger_sort(nums, left, mid, temp);
        merger_sort(nums, mid + 1, right, temp);
        //合并，没分一次便合并一次
        merge(nums, left, mid, right, temp);
    }
    public static void merge(int[] nums, int left, int mid, int right, int[] temp){
        int i = left, j = mid + 1;
        int t = 0;
        //进行二路归并
        while(i <= mid && j <= right){
            if(nums[i] < nums[j]){
                temp[t++] = nums[i++];
            }
            else{
                temp[t++] = nums[j++];
            }
        }
        //左边还有剩余
        while(i <= mid){
            temp[t++] = nums[i++];
        }
        //右边还有剩余
        while(j <= right){
            temp[t++] = nums[j++];
        }

        //将temp数组的元素拷贝到nums
        //并不是每次都拷贝所有数据
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            //将归并的这一段复制到原来数组
            nums[tempLeft++] = temp[t++];
        }
    }

}
